/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-11-14
 * Time: 17:12
 */

class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode max = new ListNode(0);
        ListNode min = new ListNode(0);
        ListNode maxE = max;
        ListNode minE = min;

        ListNode cur = head;
        while (cur != null) {
            if (cur.val >= x) {
                maxE.next = cur;
                maxE = maxE.next;
            }else {
                minE.next = cur;
                minE = minE.next;
            }
            cur = cur.next;
        }

        if (min.next == null) {
            return max.next;
        }

        maxE.next = null;
        minE.next = max.next;
        return min.next;
    }
}
